import java.util.*;
class TreeNode {
   int val = 0;
   TreeNode left = null;
   TreeNode right = null;
 }


public class Test {
    /*
    题目 1：二叉树中和为某一值的路径（一）
     */
    public boolean hasPathSum (TreeNode root, int sum) {
        if(root == null){
            return false;
        }

        return search(root, sum);
    }

    private boolean search(TreeNode curNode, int sum){
        // 递归结束的条件
        if(curNode == null){
            return false;
        }

        sum -= curNode.val;

        // 看看是不是叶子节点，并且 sum = 0
        if(curNode.left == null && curNode.right == null && sum == 0){
            return true;
        }

        return search(curNode.left, sum) || search(curNode.right, sum);
    }

    /*
    题目 2：判断是不是完全二叉树
     */
    public boolean isCompleteTree (TreeNode root) {
        // 空树肯定是 完全二叉树！
        if(root == null){
            return true;
        }

        LinkedList<TreeNode> queue = new LinkedList<>();

        queue.offer(root);

        // 设置一个标记
        boolean isComplete = false;

        while(!queue.isEmpty()){
            TreeNode cur = queue.poll();

            // 记录下第一次 cur 为 null 时：
            if(cur == null){
                isComplete = true;
                continue;
            }

            // 当 cur 不为 null 而 isComplete 为 true 时，证明不是完全二叉树：
            if(isComplete){
                return false;
            }

            queue.offer(cur.left);
            queue.offer(cur.right);
        }
        return true;
    }

    /*
    题目3 ：判断是不是平衡二叉树
     */
    public boolean IsBalanced_Solution(TreeNode root) {
        if(root == null){
            return true;
        }

        int ret = height(root);
        if(ret == -1){
            return false;
        }else{
            return true;
        }
    }

    private int height(TreeNode root){
        if(root == null){
            return 0;
        }

        int left = height(root.left);
        if(left < 0){
            return -1;
        }
        int right = height(root.right);
        if(right < 0){
            return -1;
        }

        if(Math.abs(left - right) < 2){
            return Math.max(left, right) + 1;
        }else{
            return -1;
        }
    }

    // 可进一步修改如下：
    public boolean IsBalanced_Solution1(TreeNode root) {
        if(root == null){
            return true;
        }

        return height(root) != -1;
    }

    private int height1(TreeNode root){
        if(root == null){
            return 0;
        }

        int left = height(root.left);
        if(left < 0){
            return -1;
        }

        int right = height(root.right);
        if(right < 0){
            return -1;
        }

        return Math.abs(left - right) > 1 ? -1 : Math.max(left, right) + 1;
    }


}
